Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four

摘要

Håstad established that any predicate P⊆{0,1}m containing Parity of width at least three is approximation resistant for almost-satisfiable instances. In comparison to, for example, the approximation hardness of 3SAT, this general result however left open the hardness of perfectly-satisfiable instances. This limitation was addressed by O'Donnell and Wu, and subsequently generalized by Huang, to show the threshold result that predicates strictly containing Parity of width at least three are approximation resistant also for perfectly-satisfiable instances, assuming the d-to-1 Conjecture. We extend modern hardness-of-approximation techniques by Mossel et al., eliminating the dependency on projection degrees for a special case of decoupling/invariance and -- when reducing from Smooth Label Cover -- the dependency on projection degrees for noise introduction. Tools in hand, we prove the same approximation-resistance result for predicates of width at least four, subject only to P ≠ NP. A preliminary version of this paper appeared in the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'12).